//二叉链表（Binary Linked List）
//—— 二叉树专用
#include<stdio.h>
#include<stdlib.h>

//
typedef struct TreeNode{
    int data;
    struct TreeNode* left;    
    struct TreeNode* right;    
}TreeNode,*BiTree;

//
TreeNode* CreateNode(int data){
    TreeNode* newNode =(TreeNode*)malloc(sizeof(TreeNode));
    if(newNode==NULL){
        printf("no neicun\n");
        exit(1);
    }
    newNode->data=data;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode;
}

//
void insertNode(BiTree* root,int data){
    //
    if(*root==NULL){
        *root=CreateNode(data);
        return;
    }
    //
    if(data<(*root)->data){
        //
        insertNode(&((*root)->left),data);

    }else if (data>(*root)->data)
    {
        /* code */
        insertNode(&((*root)->right),data);
    }

    
}

//root->left->right
void preOrder(BiTree root){
    if(root!=NULL){
        printf("%d ",root->data);
        preOrder(root->left);
        preOrder(root->right);
    }

}

//
void inOrder(BiTree root){
    if(root!=NULL){
        preOrder(root->left);
        printf("%d ",root->data);
        preOrder(root->right);
    }

}

//
//
void postOrder(BiTree root){
    if(root!=NULL){
        preOrder(root->left);
        preOrder(root->right);
        printf("%d ",root->data);
    }

}

//
void destroyTree(BiTree root){
    if(root!=NULL){
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);

    }
}

//
int main(){
    BiTree root =NULL;

    //
      // 插入节点构建二叉搜索树（数据可自定义）
    insertNode(&root, 50);  // 根节点
    insertNode(&root, 30);  // 50的左子树
    insertNode(&root, 70);  // 50的右子树
    insertNode(&root, 20);  // 30的左子树
    insertNode(&root, 40);  // 30的右子树
    insertNode(&root, 60);  // 70的左子树
    insertNode(&root, 80);  // 70的右子树
    
     // 打印三种遍历结果（验证树结构是否正确）
    printf("二叉链表（二叉搜索树）遍历结果：\n");
    printf("前序遍历（根→左→右）：");
    preOrder(root);  // 预期输出：50 30 20 40 70 60 80
    printf("\n");

    printf("中序遍历（左→根→右）：");
    inOrder(root);   // 预期输出：20 30 40 50 60 70 80（升序，二叉搜索树特性）
    printf("\n");

    printf("后序遍历（左→右→根）：");
    postOrder(root); // 预期输出：20 40 30 60 80 70 50
    printf("\n");

    // 销毁树（必须释放内存，避免内存泄漏）
    destroyTree(root);
    root = NULL;  // 销毁后将根指针置为NULL，避免野指针

    return 0;


}
